package class_4;

public class Coding_nthUglyNumber {
	public static int nthUglyNumber(int n) {
		int[] dp = new int[n+1];//丑数缓存表
		dp[1] = 1;//默认第一个丑数为1
		int a,b,c;
		int cur = 0;
		for(int i=2,i2=1,i3=1,i5=1;i<n+1;i++) {
			a = dp[i2] * 2;
			b = dp[i3] * 3;
			c = dp[i5] * 5;
			cur = Math.min(Math.min(a, b), c);
			//为什么不写if---else-if---else逻辑？
			// cur可能满足==a, ==b, ==c。这意味对应的指针都要往后前进。
			if(cur == a) {
				i2++;
			}
			if(cur == b) {
				i3++;
			}
			if(cur == c) {
				i5++;
			}
			dp[i] = cur;
		}
		return dp[n];
	}
}
